1. Field of the Invention
The present invention relates generally to a method and system of variable block-size motion estimation and more particularly, to a method and system of fast variable block-size motion estimation based on merge and split procedures for H.264/MPEG-4 AVC video encoding.
2. Background of the Invention
In current video coding standards, Motion Estimation (ME) is a core functional block to remove temporal redundancy in video sequences to achieve high compression. In the emerging H.264/MPEG-4 AVC video coding standard, for Inter coded Macroblocks (MBs), tree-structured block-sizes can be employed in the motion estimation. Each 16*16 MB can be coded in 16*16, 16*8, 8*16, and 8*8 block-modes. If the 8*8 block-mode is chosen, each 8*8 sub-macroblock can be independently partitioned into 8*8, 8*4, 4*8, and 4*4 blocks. So, altogether there can be seven different block-sizes: 16*16, 16*8, 8*16, 8*8, 8*4, 4*8, and 4*4. For these block-sizes, each 16*16 MB contains 1, 2, 2, 4, 8, 8, and 16 blocks respectively.
In the H.264/MPEG-4 AVC reference software, a Fast Full Search (FFS) algorithm is used for the ME. The SADs (Sum of Absolute Differences) of 4*4 blocks are first calculated and the SADs of the other six block-modes are calculated by summing up the SADs of the corresponding 4*4 blocks. Although the SADs in the calculation of the 4*4 block-mode are re-used, for all seven block-sizes, the SAD calculation load will be larger than that using a full-search ME for a 16*16 MB. For example, if a search-window size is 31*31 pixels and the Unrestricted Motion Vector (UMV) mode is enabled, the number of search points using the full-search ME is 31*31=961. Accordingly, the required SAD computation is larger than that for a 16*16 MB with 961 search points, which requires a lot of computations.
Recently some fast variable block-size ME algorithms have been proposed. For example, a fast search algorithm is applied to the seven block-sizes independently, as disclosed by Ma et al. in an article entitled “An Improved Adaptive Rood Pattern Search For Fast Block-matching Motion Estimation in JVT/H.26L”. A merge procedure is also proposed, as disclosed by Tu et al. in “Fast Variable-size Block Motion Estimation Using Merging Procedure With an Adaptive Threshold”, which determines the MVs of larger block-sizes from the MVs of smaller block-sizes, with the threshold for the merge criteria related to the quantization parameter. Kucukgoz et al. in their article entitled “Early-stop and Motion Vector Re-using for MPEG-2 to H.264 Transcoding” apply a bottom-up merge scheme and an early-stop strategy for the variable block-size ME in MPEG-2 to H.264 transcoding. Furthermore, in “Fast Integer Pixel Motion Estimation” disclosed by Li et al., a merge and split process for the ME is proposed. The disclosure, however, fails to describe the detailed process.